﻿#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#include <climits>
using namespace std;

string longestPalindrome(string s) 
{
	int n = s.size();
	vector<vector<bool> > dp(n, vector<bool>(n));

	int len = 1;
	int begin = 0;								// 标记最长子串的起始位置和⻓度
	// 填表，从下往上填
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = i; j < n; j++)
		{
			if (s[i] == s[j])
			{
				dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
			}
			if (dp[i][j] && j - i + 1 > len)	// 找出子串中最⻓的回⽂⼦串
			{
				len = j - i + 1;
				begin = i;
			}
		}
	}
	return s.substr(begin, len);
}
int main()
{
	string s = "aba";

	cout << longestPalindrome(s) << endl;
	return 0;
}
